package Statistics;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

/**
 * @author Xenophon
 * @version 2010-1-16
 *
 */
public class TarjanSCC {
	private static int count = 0;
	private static int index = 0;
	private static Stack<String> dataStack = new Stack<String>();
	
	private static Set<Set<String>> result = new HashSet<Set<String>>();
	
	private static HashMap<String, IDGraphNode> dataPool; 
	private static HashMap<String, Utility> vertices = new HashMap<String, Utility>();
	
	private static IDGraph subGraph;
	
	private static class Utility
	{
		public String id;
		public int index = -1;
		public int lowlink;
		public boolean equals(Object o)
		{
			if(o instanceof Utility)
			{
				return id.equals(((Utility)o).id);
			}
			return false;
		}
		public int hashCode()
		{
			return id.hashCode();
		}
	}
	
	public static void CalculateSCC(IDGraph graph)
	{	
		dataPool = graph.GetNodeMap();
		for(String id: dataPool.keySet())
		{
			Utility u = new Utility();
			u.id = id;
			vertices.put(id, u);
		}
		
		for(Map.Entry<String, Utility> entry:vertices.entrySet())
		{
			if(entry.getValue().index == -1)
				Tarjan(entry.getKey());
		}
	}
	
	public static void Tarjan(String id)
	{
		Utility u = vertices.get(id);
		u.index = index;
		u.lowlink = index;
		index++;
		
		dataStack.push(id);
		
		for(String sink:dataPool.get(id).GetOutEdges().keySet())
		{
			if(vertices.get(sink).index==-1)
			{
				Tarjan(sink);
				int lowLinkOfSink = vertices.get(sink).lowlink;
				u.lowlink = u.lowlink > lowLinkOfSink?lowLinkOfSink:u.lowlink;
			}else{
				int indexOfSink = vertices.get(sink).index;
				u.lowlink = u.lowlink > indexOfSink?indexOfSink:u.lowlink;
			}
		}
		
		if(u.index == u.lowlink)
		{
			HashSet<String> scc = new HashSet<String>();
			String res = null;
			do{
			   if(dataStack.isEmpty())
				   break;
			   res = dataStack.pop();
			   scc.add(res);
			}while(!res.equals(u.id));
			result.add(scc);
			count++;
			System.out.println("SCC "+count+" : "+scc.size());
		}
	}
	
	public static void CalculateCC(IDGraph graph)
	{
		dataPool = graph.GetNodeMap();
		for(String id: dataPool.keySet())
		{
			Utility u = new Utility();
			u.id = id;
			vertices.put(id, u);
		}
		
		for(Map.Entry<String, Utility> entry:vertices.entrySet())
		{
			HashSet<String> cc = new HashSet<String>();
 			if(entry.getValue().index == -1)
				BFS(entry.getKey(),cc);
 			result.add(cc);
			count++;
			System.out.println("CC "+count+" : "+cc.size());
		}
	}
	
	public static void BFS(String source,HashSet<String> result)
	{
		Utility u = vertices.get(source);
		u.index = 0;//we've visited
		result.add(source);
		
		for(String sink:dataPool.get(source).GetOutEdges().keySet())
		{
			if (vertices.get(sink).index == -1)
				BFS(sink, result);
		}
	}
	
	public static Set<Set<String>> GetSCCs(){return result;}
	
	public static IDGraph GetSubGraph(IDGraph graph, String node, int count)
	{
		int now = 0;
		HashMap<String, IDGraphNode> nodeMap = graph.GetNodeMap();
		if(count<1||count>500||!nodeMap.containsKey(node))
		{
			return null;
		}
		
		subGraph = new IDGraph();
		Stack<String> tier = new Stack<String>();
		tier.push(node);
		now++;
		BFScalculateSubGraph(graph.GetNodeMap(),tier,now,count);
		return subGraph;
	}
	
	protected static void BFScalculateSubGraph(HashMap<String, IDGraphNode> nodeMap,Stack<String> tier,int now,int count)
	{
		Stack<String> newTier = new Stack<String>();
		while(tier.size()>0&&now<count)
		{
			String source = tier.pop();
			for (String sink:nodeMap.get(source).GetOutEdges().keySet()){
				if(now>=count)
					return;
				if(subGraph.GetNodeMap().keySet().contains(sink))
					continue;
				subGraph.AddNode(sink);
				subGraph.AddEdge(source, sink);
				newTier.add(sink);
				now++;
			}
		}
		if(now<count&&newTier.size()>0)
			BFScalculateSubGraph(nodeMap, newTier, now, count);
			
	}
}
